package Graph.directGraph;

import Graph.graphWithWeight.GraphWeight;

import java.util.Arrays;

/**
 * @Author: 蔡翔
 * @Date: 2020/3/23 20:41
 * @Version 1.0
 */
public class Floyed {
    private DirectGraph G;
    private int[][] dis;
    private boolean hasNegativeCycle;

    //Floyed 不用传入原点，因为它会计算任意两点之间的最短路径
    public Floyed(DirectGraph g){
        this.G = g;
        //表示两点的最短路径
        dis = new int[G.V()][G.V()];

        //先把所有边赋值为 最大值
        for(int i=0;i<G.V();i++){
            Arrays.fill(dis[i],Integer.MAX_VALUE);
        }

        //给边初始化
        for(int v=0;v<G.V();v++){
            //自己到自己的距离是0
            dis[v][v] = 0;

            for(int w:G.adj(v)){
                dis[v][w] = G.getWeight(v,w);
            }
        }

        for(int t=0;t<G.V();t++){
            for(int v=0;v<G.V();v++){
                for(int w=0;w<G.V();w++){
                    if(dis[v][t]!=Integer.MAX_VALUE && dis[t][w]!=Integer.MAX_VALUE &&dis[v][t]+dis[t][w]<dis[v][w]){
                        dis[v][w] = dis[v][t]+dis[t][w];
                    }
                }
            }
        }
        //floyed算法也可以用来检测负权环 ： dis[v][v]<0  自己到自己如果小于0那么必定存在负权环（也就是需要判定这个方阵的对角线 是否存在不是0的点）
        //核心也就是 判断 每个点边上是否存在负权边，，只不过是用 dis[v][t]+dis[t][v]<dis[v][v]  来判定的。
        for(int v=0;v<G.V();v++){
            if(dis[v][v]<0){
                hasNegativeCycle = true;
            }
        }

    }

    public boolean hasNegCycle(){
        return hasNegativeCycle;
    }

    public boolean isConnectedTo(int v,int w){
        G.validateVertex(v);
        G.validateVertex(w);
        return dis[v][w]!=Integer.MAX_VALUE;
    }

    public int disTo(int v,int w){
        return dis[v][w];
    }

    public static void main(String[] args) {
        DirectGraph g = new DirectGraph("wg2.txt",true);
        Floyed f = new Floyed(g);
        if(!f.hasNegativeCycle){
            for(int v=0;v<g.V();v++){
                for(int w=0;w<g.V();w++){
                    System.out.print(f.disTo(v,w)+" ");
                }
                System.out.println();

            }
        }else {
            System.out.println("有负权环");
        }
    }

}
